package com.cty._02_HighQualityCode._23_EntryNodeInListLoop;

/**
 * @Auther: cty
 * @Date: 2020/7/8 12:41
 * @Description: 面试题23：链表中环的入口结点
 * 题目：一个链表中包含环，如何找出环的入口结点？例如，在图3.8的链表中，
 * 环的入口结点是结点3。
 * @version: 1.0
 */
class ListNode {
    int value;
    ListNode next;

    public ListNode(){}

    public ListNode(int value){
        this.value = value;
    }

}  // end class

class LinkedList {
    private ListNode first;

    public LinkedList(){
        this.first = null;
    }

    public boolean isEmpty(){
        return first == null;
    }

    public void displayList(){
        ListNode current = first;
        while(current != null) {
            System.out.print(current.value);
            current = current.next;
        }
        System.out.println();
    }

    public void insertFirst(ListNode node){
        node.next = first;
        first = node;
    }

    /**
     * 判断是否存在环
     * @return
     *      若存在，返回环中的一个节点
     *      若不存在，返回null
     */
    public ListNode hasLoop(){
        if(isEmpty())
            return null;

        ListNode slowPtr = first;
        ListNode fastPtr = first;
        if(fastPtr.next == null)
            return null;  // 只有一个节点且无环

        fastPtr = fastPtr.next;
        while(fastPtr.next != null){
            if(fastPtr == slowPtr)  // 快指针追上慢指针
                return fastPtr;

            fastPtr = fastPtr.next;
            if(fastPtr.next != null)
                fastPtr = fastPtr.next;

            slowPtr = slowPtr.next;
        }
        return null;
    }  // end hasLoop()

    /**
     * 查找链表中环的入口节点
     * @return
     *      若有环，返回环入口节点
     *      若没有环，返回null
     */
    public ListNode findEntryNode(){
        ListNode nodeInLoop = hasLoop();
        if(nodeInLoop == null)
            return null;  // 没有环，自然没有环入口

        ListNode temp = nodeInLoop;
        int numberOfLoop = 1;  // 当前所在节点也是环中的一个节点
        while(temp.next!=null && temp.next!=nodeInLoop){
            numberOfLoop++;
            temp = temp.next;
        }

        ListNode aheadPtr = first;
        ListNode behindPtr = first;
        for(int i=0; i<numberOfLoop; i++)
            aheadPtr = aheadPtr.next;

        while(aheadPtr != behindPtr){
            aheadPtr = aheadPtr.next;
            behindPtr = behindPtr.next;
        }
        return aheadPtr;
    }  // end findEntryNode()

}  // end class
